1466D - 13th Labour of Heracles - CodeForces Solution

#include <iostream>
#include <bits/stdc++.h>
// #include "utilities.cpp"
using namespace std;
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define forn(i, x, n) for (int i = x; i < n; i++)
#define vi vector<int>
#define vpp vector<pair<int,int>>
#define vs vector<string>
#define vll vector<long long>
#define mod 1000000007; 
int row[] = {1,0,-1,0};
int col[] = {0,1,0,-1};


void solve(){

    int n;
    cin>>n;

    vpp wt(n); 
    vi inD(n+1, -1);
    int sum = 0;
    forn(i,0,n){
        cin>>wt[i].first;
        sum += wt[i].first;
        wt[i].second = i+1;
    }
    vector<int> adj[n];

    forn(i,0,n-1){

        int a, b;
        cin>>a>>b;
        inD[a]++;
        inD[b]++;
    }

    sort(rall(wt));
    int j = 0;
    cout<<sum<<' ';

    forn(i, 1, n-1){

        if(j == wt.size()){
            cout<<sum<<' ';
        }else{

            int k = wt[j].second;
            while(inD[k] <= 0){

                j++;
                if(j == wt.size()) break;
                k = wt[j].second;
            } 
            if(j == wt.size()){
                cout<<sum<<' ';
            }else{

                inD[k]--;
                sum += wt[j].first;
                cout<<sum<<' ';
            }
        }
    }
    cout<<'\n';
}


signed main(){
    int t = 1; 
    cin >> t;
    while (t--) solve();    
    return 0;
}